<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>构建二叉树</title>
  </head>

  <body>
    <script>
      function BinarySearchTree() {
        function Node(key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }
        this.root = null;

        BinarySearchTree.prototype.insert = function (key) {
          var newNode = new Node(key);
          if (this.root == null) {
            this.root = newNode;
          } else {
            this.insertNode(this.root, newNode);
          }
        };
        BinarySearchTree.prototype.insertNode = function (node, newNode) {
          if (node.key > newNode.key) {
            if (node.left == null) {
              node.left = newNode;
            } else {
              this.insertNode(node.left, newNode);
            }
          } else {
            if (node.right == null) {
              node.right = newNode;
            } else {
              this.insertNode(node.right, newNode);
            }
          }
        };
        //二叉树层序遍历
        BinarySearchTree.prototype.print = function () {
          const q = [];
          q.push(this.root);
          while (q.length) {
            const node = q.pop();
            if (node != null) {
              console.log(node.key);
              if (node.left != null) {
                q.unshift(node.left);
              }
              if (node.right != null) {
                q.unshift(node.right);
              }
            }
          }
        };
        // 二叉树前序遍历
        BinarySearchTree.prototype.preOrder = function (handler) {
          this.preOrderNode(this.root, handler);
        };
        BinarySearchTree.prototype.preOrderNode = function (node, handler) {
          if (node != null) {
            handler(node.key);
            this.preOrderNode(node.left, handler);
            this.preOrderNode(node.right, handler);
          }
        };
        // 二叉树中序遍历
        BinarySearchTree.prototype.midOrder = function (handler) {
          this.midOrderNode(this.root, handler);
        };
        BinarySearchTree.prototype.midOrderNode = function (node, handler) {
          if (node != null) {
            this.midOrderNode(node.left, handler);
            handler(node.key);
            this.midOrderNode(node.right, handler);
          }
        };
        // 二叉树后序遍历
        BinarySearchTree.prototype.postOrder = function (handler) {
          this.postOrderNode(this.root, handler);
        };
        BinarySearchTree.prototype.postOrderNode = function (node, handler) {
          if (node != null) {
            this.postOrderNode(node.left, handler);
            this.postOrderNode(node.right, handler);
            handler(node.key);
          }
        };
        // 获取二叉树中的最大最小值
        BinarySearchTree.prototype.min = function () {
          var node = this.root;
          while (node.left != null) {
            node = node.left;
          }
          return node.key;
        };
        BinarySearchTree.prototype.max = function () {
          var node = this.root;
          while (node.right != null) {
            node = node.right;
          }
          return node.key;
        };
        // 在二叉树中搜索特定的值
        BinarySearchTree.prototype.search = function (key) {
          // var node = this.root;
          // while (node != null) {
          //     if (node.key > key) {
          //         node = node.left;
          //     } else if (node.key < key) {
          //         node = node.right;
          //     } else {
          //         return true
          //     }
          // }
          // return false;

          return this.searchNode(this.node, key);
        };
        BinarySearchTree.prototype.searchNode = function (node, key) {
          if (node === null) {
            return false;
          }
          if (node.key > key) {
            return this.searchNode(node.left, key);
          } else if (node.key < key) {
            return this.searchNode(node.right);
          } else {
            return true;
          }
        };
        BinarySearchTree.prototype.remove = function (key) {
          let current = this.root;
          let parent = this.root;
          let isLeft = false;
          while (current.key != key) {
            parent = current;
            if (key < current.key) {
              current = current.left;
              isLeft = true;
            } else {
              current = current.right;
              isLeft = false;
            }
            // 没有找到要删除的结点
            if (current == null) {
              return false;
            }
          }

          // 找到相应的结点，根据情况删除结点
          // 删除的结点是叶子结点
          if (current.left == null && current.right == null) {
            if (current == this.root) {
              this.root = null;
            } else if (isLeft) {
              parent.left = null;
            } else {
              parent.right = null;
            }
          }
          // 删除的结点只有一个子节点
          else if (current.right == null) {
            if (this.root == current) {
              this.root = current.left;
            } else if (isLeft) {
              parent.left = current.left;
            } else {
              parent.left = current.right;
            }
          } else if (current.left == null) {
            if (this.root == current) {
              this.root = current.right;
            } else if (isLeft) {
              parent.left = current.right;
            } else {
              parent.right = current.right;
            }
          }
          // 删除的结点有两个子节点
          else {
            // 获取后继节点
            var successor = this.getSuccessor(current);
            // 判断是否是根节点
            if (current == this.root) {
              this.root = successor;
            } else if (isLeft) {
              parent.left = successor;
            } else {
              parent.right = successor;
            }
            successor.left = current.left;
          }
        };
        // 寻找后继节点
        BinarySearchTree.prototype.getSuccessor = function (delNode) {
          // 定义变量，保存找到的后继
          var successor = delNode;
          var current = delNode.right;
          var successorParent = delNode;

          // 循环查找
          while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
          }
          // 判断寻找的后继节点是否直接就是delNode的right节点
          if (successor != delNode.right) {
            successorParent.left = successor.right;
            successor.right = delNode.right;
          }
          return successor;
        };
      }

      var bst = new BinarySearchTree();
      bst.insert(11);
      bst.insert(7);
      bst.insert(15);
      bst.insert(5);
      bst.insert(9);
      bst.insert(13);
      bst.insert(20);
      bst.insert(3);
      bst.insert(6);
      bst.insert(8);
      bst.insert(10);
      bst.insert(12);
      bst.insert(14);
      bst.insert(18);
      bst.insert(25);
      // bst.print()
      // bst.postOrder(function (key) {
      //     console.log(key)
      // })
      // console.log(bst.min())
      // console.log(bst.max())
      // console.log(bst.search(3));
      bst.remove(9);
      bst.remove(7);
      bst.remove(15);
      bst.postOrder(function (key) {
        console.log(key);
      });
    </script>
  </body>
</html>
